{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Can I Win"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #memoization #math #dynamic-programming #bitmask #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #记忆化搜索 #数学 #动态规划 #状态压缩 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canIWin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #我能赢吗"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在 \"100 game\" 这个游戏中，两名玩家轮流选择从 <code>1</code> 到 <code>10</code> 的任意整数，累计整数和，先使得累计整数和 <strong>达到或超过</strong>&nbsp; 100 的玩家，即为胜者。</p>\n",
    "\n",
    "<p>如果我们将游戏规则改为 “玩家 <strong>不能</strong> 重复使用整数” 呢？</p>\n",
    "\n",
    "<p>例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 &gt;= 100。</p>\n",
    "\n",
    "<p>给定两个整数&nbsp;<code>maxChoosableInteger</code>&nbsp;（整数池中可选择的最大数）和&nbsp;<code>desiredTotal</code>（累计和），若先出手的玩家能稳赢则返回 <code>true</code>&nbsp;，否则返回 <code>false</code> 。假设两位玩家游戏时都表现 <strong>最佳</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>maxChoosableInteger = 10, desiredTotal = 11\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：\n",
    "</strong>无论第一个玩家选择哪个整数，他都会失败。\n",
    "第一个玩家可以选择从 1 到 10 的整数。\n",
    "如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。\n",
    "第二个玩家可以通过选择整数 10（那么累积和为 11 &gt;= desiredTotal），从而取得胜利.\n",
    "同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>maxChoosableInteger = 10, desiredTotal = 0\n",
    "<b>输出：</b>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>maxChoosableInteger = 10, desiredTotal = 1\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= maxChoosableInteger &lt;= 20</code></li>\n",
    "\t<li><code>0 &lt;= desiredTotal &lt;= 300</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [can-i-win](https://leetcode.cn/problems/can-i-win/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [can-i-win](https://leetcode.cn/problems/can-i-win/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n11', '10\\n0', '10\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, n: int, t: int) -> bool:\n",
    "        A=[1, 3, 55, 239, 31711, 122815, 266321791, 987627263, 35115484577279, 129119532612607, 73750924364978583551, 269889437802182995967, 2475577798400419164825051135, 9053323986490065564353937407, 1329187429340872680135158647714971647, 4860109011762223111204153015693934591, 11417894428481647648755042934333073416454537215, 41747337975307957741065316758769028045853163519, 1569272440683756973210438225605354033835738289743391621119, 5737675090290529395075956564207170326746932471447052877823]\n",
    "        return bool((A[n-1]>>max(t-1,0))&1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        max_sum = maxChoosableInteger*(maxChoosableInteger+1)//2\n",
    "        if max_sum < desiredTotal:\n",
    "            return False\n",
    "        elif max_sum == desiredTotal:\n",
    "            return (maxChoosableInteger % 2 == 1)\n",
    "\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True\n",
    "\n",
    "        bit_mask = 1 << maxChoosableInteger\n",
    "        self.record = {}\n",
    "\n",
    "        return self.checkWin(maxChoosableInteger, bit_mask, desiredTotal)\n",
    "\n",
    "    def checkWin(self, max_num, bit_mask, remain_sum):\n",
    "\n",
    "        if bit_mask in self.record:\n",
    "            return self.record[bit_mask]\n",
    "\n",
    "        for i in range(max_num):\n",
    "            if (1 & (bit_mask >> i)) != 0:\n",
    "                continue\n",
    "\n",
    "            n = i+1\n",
    "            if (n >= remain_sum) or (self.checkWin(max_num, bit_mask | (1 << i), remain_sum-n) is False):\n",
    "                self.record[bit_mask] = True\n",
    "                return True\n",
    "\n",
    "        self.record[bit_mask] = False\n",
    "        return False\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger>desiredTotal:\n",
    "            return True\n",
    "        if (1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal:\n",
    "            return False\n",
    "        \n",
    "\n",
    "        def helper(state,remainTotal,dp):\n",
    "            if dp[state]!=None:\n",
    "                return dp[state]\n",
    "            for i in range(1,maxChoosableInteger+1):\n",
    "                ch = 1<<(i-1)\n",
    "                if ch & state !=0:  # 已经被选过了\n",
    "                    continue\n",
    "                if i>=remainTotal:  # 如果再直接选一张就能赢，则当前状态一定赢\n",
    "                    dp[state] = True\n",
    "                    return True\n",
    "                if not helper(ch | state,remainTotal-i,dp):  # 如果对方选牌没有赢\n",
    "                    dp[state] = True\n",
    "                    return True\n",
    "            dp[state]=False  # 不能赢就肯定输\n",
    "            return False\n",
    "        \n",
    "        return helper(0,desiredTotal,[None]*(2**maxChoosableInteger-1))\n",
    "                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal: return True\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: return False\n",
    "\n",
    "        def dfs(state, desiredTotal, dp):\n",
    "            if dp[state] != None:\n",
    "                return dp[state]\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                cur = 1 << (i - 1)\n",
    "                if cur & state != 0:\n",
    "                    continue\n",
    "                \n",
    "                if i >= desiredTotal or not dfs(cur | state, desiredTotal - i, dp):\n",
    "                    dp[state] = True\n",
    "                    return True\n",
    "            dp[state] = False\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, desiredTotal, [None] * (1 << maxChoosableInteger))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        # 这里可以从二维缩减到一维，否则内存超出，是因为从state可以推出rest\n",
    "        self.memo = [None for _ in range(1 << (maxChoosableInteger - 1) + 1)]\n",
    "        state = 0\n",
    "        return self.dp(maxChoosableInteger, state, desiredTotal)\n",
    "\n",
    "    def dp(self, choose, state, rest):\n",
    "        if rest <= 0:\n",
    "            return False\n",
    "        if self.memo[state] != None:\n",
    "            return self.memo[state]\n",
    "        res = False\n",
    "        for i in range(1, choose + 1):\n",
    "            if (1 << (i - 1)) & state == 0:\n",
    "                if not self.dp(choose, state | (1 << (i - 1)), rest - i):\n",
    "                    res = True\n",
    "                    # 找到可以赢的方式就break\n",
    "                    break\n",
    "        self.memo[state] = res\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger*(1+maxChoosableInteger)/2<desiredTotal:\n",
    "            return False\n",
    "        visit=[0]*(1<<21)\n",
    "        if not desiredTotal : return True\n",
    "        return self.dfs(maxChoosableInteger, desiredTotal,0,0,visit)\n",
    "    \n",
    "    def dfs(self,maxChoosableInteger, desiredTotal,Sum,choose,visit):\n",
    "        #print(choose)\n",
    "        if visit[choose]==1: return True\n",
    "        elif visit[choose]==2: return False\n",
    "        for i in range(1,maxChoosableInteger+1):\n",
    "            num=(1<<i)\n",
    "            if not(num&choose): \n",
    "            \tif(Sum+i>=desiredTotal):\n",
    "                \tvisit[choose]=1\n",
    "                \treturn True\n",
    "            \tif not (self.dfs(maxChoosableInteger, desiredTotal,Sum+i,choose|num,visit)):\n",
    "                \tvisit[choose]=1\n",
    "                \treturn True\n",
    "        visit[choose]=2\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # visited[i] == 0 means not computed yet\n",
    "        # visited[i] == 1 means computed and the result is True\n",
    "        # visited[i] == 2 means computed and the result is False\n",
    "        self.visited = [0]*(1<<21)\n",
    "    def dfs(self, state, sum, maxChoosableInteger, desiredTotal) -> bool:\n",
    "            if self.visited[state]==1: return True\n",
    "            if self.visited[state]==2: return False\n",
    "            for x in range(1, maxChoosableInteger+1):\n",
    "                # 如果数字已经被使用\n",
    "                if (1<<x)&state: continue\n",
    "                if sum+x>=desiredTotal:\n",
    "                    self.visited[state] = 1\n",
    "                    return True\n",
    "                if not self.dfs( (1<<x)|state, x+sum, maxChoosableInteger, desiredTotal):\n",
    "                    self.visited[state] = 1\n",
    "                    return True\n",
    "            self.visited[state] = 2\n",
    "            return False\n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger>=desiredTotal:\n",
    "            return 1>0\n",
    "        if maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal:\n",
    "            return 1<0\n",
    "\n",
    "        return self.dfs(0,0,maxChoosableInteger,desiredTotal)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        def backtrack(nums):\n",
    "            x = tuple(sorted(list(nums)))\n",
    "            if x in mem:\n",
    "                return mem[x]\n",
    "            for i in range(maxChoosableInteger, 0, -1):\n",
    "                if i not in nums:\n",
    "                    if sum(nums) + i >= desiredTotal:\n",
    "                        mem[x] = True\n",
    "                        return True\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                if i not in nums:\n",
    "                    nums.add(i)\n",
    "                    if backtrack(nums):\n",
    "                        nums.remove(i)\n",
    "                    else:\n",
    "                        nums.remove(i)\n",
    "                        mem[x] = True\n",
    "                        return True\n",
    "            mem[x] = False\n",
    "            return False\n",
    "\n",
    "        if maxChoosableInteger * (1 + maxChoosableInteger) // 2 < desiredTotal:\n",
    "            return False\n",
    "        mem = {}\n",
    "        return backtrack(set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 由暴力尝试的位信息方法，改为，位信息缓存的，状态压缩方式\n",
    "    # 1~choose 拥有的数字\n",
    "\t# total 一开始的剩余\n",
    "\t# 返回先手会不会赢\n",
    "    def canIWin(self, choose, total):\n",
    "        if total == 0:\n",
    "            return True\n",
    "\n",
    "        if choose * (choose + 1) >> 1 < total:\n",
    "            return False\n",
    "        \n",
    "        # 缓存用的dp\n",
    "        # 可以存放status的数量，来决定缓存的数量\n",
    "        #   相同的status，肯定是相同的返回值（是否拿取后，是成功的）\n",
    "        dp = [0 for i in range(1 << (choose + 1))]\n",
    "        \n",
    "        # dp[status] == 1  true # 代表，当前状态选择下，返回值是成功的True\n",
    "\t\t# dp[status] == -1  false\n",
    "\t\t# dp[status] == 0  process(status) 没算过！去算！\n",
    "        return self.process2(choose, 0, total, dp)\n",
    "    \n",
    "    # 当前轮到先手拿，\n",
    "\t# 先手可以拿1~choose中的任何一个数字\n",
    "    #   用status，记录，choose中的数字，是否被拿\n",
    "    #   status,当做一个值，缓存到dp中，以后遇到相同的状态，就直接读取值\n",
    "\t# 还剩rest这么多值，\n",
    "    #   因为rest是，可以被status，这个值，算出来，所以，只有status是变量。详见注释1\n",
    "\t# 返回先手会不会赢\n",
    "\n",
    "    # 为什么明明status和rest是两个可变参数，却只用status来代表状态(也就是dp)\n",
    "\t#   因为选了一批数字之后，得到的和一定是一样的，\n",
    "    #   所以rest是由status决定的，所以rest不需要参与记忆化搜索\n",
    "    #   详见注释1\n",
    "    def process2(self, choose, status, rest, dp):\n",
    "        # 先从缓存中读取值\n",
    "        if dp[status] != 0: # 当前status，已经算过了，直接读取值，返回\n",
    "            return True if dp[status] == 1 else False\n",
    "        \n",
    "        # 为了更新dp表，需要将逻辑处理后的，返回值留存下来\n",
    "        # 这里就相当于 rest <= 0的情况\n",
    "        ans = False\n",
    "        \n",
    "        if rest > 0:\n",
    "            # 这一段逻辑，和上面canIWin1的逻辑是相同的。只是增加了结果的缓存\n",
    "            for i in range(1, choose + 1, 1):\n",
    "                if ((1 << i) & status) == 0:\n",
    "                    if not self.process2(choose, (status | (1 << i)), rest - i, dp):\n",
    "                        ans = True\n",
    "                        break\n",
    "        # 当前结果，添加到缓存中\n",
    "        # 如果返回是True，就留存为1，否则为-1\n",
    "        dp[status] = 1 if ans else -1\n",
    "        # 返回当前结果\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if sum(range(1, maxChoosableInteger + 1)) < desiredTotal:\n",
    "            return False\n",
    "        s = tuple(i for i in range(1, maxChoosableInteger + 1))\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def fn(s: tuple, pre_sum: int):\n",
    "            for num in s:\n",
    "                if num + pre_sum >= desiredTotal or not fn(tuple(x for x in s if x != num), pre_sum + num):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return fn(s, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        import functools\n",
    "        if  desiredTotal <= maxChoosableInteger: return True\n",
    "        if sum(range(maxChoosableInteger + 1)) < desiredTotal: return False\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(used, desiredTotal):\n",
    "            for i in range(maxChoosableInteger):\n",
    "                cur = 1 << i\n",
    "                if cur & used == 0:\n",
    "                    if desiredTotal <= i + 1 or not dfs(cur | used, desiredTotal - i - 1):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, desiredTotal)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "@lru_cache(None)\n",
    "def dfs(state, m, goal):\n",
    "    for i in range(m):\n",
    "        if not (1<<i) & state:\n",
    "            if i+1 >= goal or not dfs(state + (1 << i), m, goal - i - 1):\n",
    "                return True\n",
    "    return False\n",
    "class Solution:\n",
    "    def canIWin(self, m: int, goal: int) -> bool:\n",
    "        if m > goal:\n",
    "            return True\n",
    "        if m * (m + 1) // 2 < goal:\n",
    "            return False\n",
    "        return dfs(0, m, goal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def helper(self, sums: List[int], dp: List[int], state: int, maxChoosableInteger: int, desiredTotal: int) -> int:\n",
    "        if dp[state] != -1:\n",
    "            return dp[state]\n",
    "\n",
    "        for i in range(1, maxChoosableInteger+1):\n",
    "            if (1<<i)&state == 0:\n",
    "                curr = state | (1<<i)\n",
    "                sums[curr] = sums[state] + i\n",
    "                if sums[curr] >= desiredTotal:\n",
    "                    dp[state] = 1\n",
    "                    return 1\n",
    "                if self.helper(sums, dp, curr, maxChoosableInteger, desiredTotal) == 0:\n",
    "                    dp[state] = 1\n",
    "                    return 1\n",
    "        \n",
    "        dp[state] = 0\n",
    "        return 0\n",
    "    \n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        s= 0 \n",
    "        for i in range(1, maxChoosableInteger+1):\n",
    "            s += i \n",
    "        if s < desiredTotal:\n",
    "            return False\n",
    "            \n",
    "        m = (1<<(maxChoosableInteger+1))\n",
    "        sums = [0]*m\n",
    "        dp = [-1]*m\n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "\n",
    "        return (self.helper(sums, dp, 0, maxChoosableInteger, desiredTotal) == 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        m = maxChoosableInteger * (maxChoosableInteger + 1) // 2\n",
    "        if desiredTotal > m:\n",
    "            return False\n",
    "        elif desiredTotal == m:\n",
    "            return maxChoosableInteger % 2 == 1\n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "        WIN = 1\n",
    "        LOSE = -1\n",
    "        PENDING = 0\n",
    "        bits = [1 << i for i in range(maxChoosableInteger)]\n",
    "        n = 1 << maxChoosableInteger\n",
    "        a = [PENDING] * n\n",
    "\n",
    "        def check(flags, s):\n",
    "            if s < desiredTotal:\n",
    "                a[flags] = LOSE\n",
    "                for i in range(maxChoosableInteger):\n",
    "                    if flags & bits[i] == 0:\n",
    "                        f = flags + bits[i]\n",
    "                        if a[f] == PENDING:\n",
    "                            check(f, s + i + 1)\n",
    "                        if a[f] == LOSE:\n",
    "                            a[flags] = WIN\n",
    "                            break\n",
    "            else:\n",
    "                a[flags] = LOSE\n",
    "        check(0, 0)\n",
    "        return a[0] == WIN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal: \n",
    "            return True \n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal: \n",
    "            return False \n",
    "        def dfs(state, total): \n",
    "            if dp[state]: \n",
    "                return dp[state] \n",
    "            for i in range(1, maxChoosableInteger + 1): \n",
    "                cur = 1 << (i - 1) \n",
    "                if state & cur: \n",
    "                    continue \n",
    "                if i >= total or not dfs(state | cur, total - i): \n",
    "                    dp[state] = True \n",
    "                    return True \n",
    "            dp[state] = False \n",
    "            return False \n",
    "        dp = [None] * (1 << maxChoosableInteger) \n",
    "        return dfs(0, desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @functools.lru_cache(maxsize=None)\n",
    "    def minimax(self, status: int, curTotal: int, doMax: bool) -> bool:\n",
    "        if status == self.allUsed:\n",
    "            return False\n",
    "        if doMax:\n",
    "            for i in range(self.maxChoosableInteger):\n",
    "                if status & (1 << i):\n",
    "                    continue\n",
    "                newStatus = status | (1 << i)\n",
    "                if curTotal + i+1  >= self.desiredTotal:\n",
    "                    return True\n",
    "                if self.minimax(newStatus, curTotal + i+1, False):\n",
    "                    return True\n",
    "            return False\n",
    "        else:\n",
    "            for i in range(self.maxChoosableInteger):\n",
    "                if status & (1 << i):\n",
    "                    continue\n",
    "                newStatus = status | (1 << i)\n",
    "                if curTotal + i+1 >= self.desiredTotal:\n",
    "                    return False\n",
    "                if not self.minimax(newStatus, curTotal + i+1, True):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        self.maxChoosableInteger = maxChoosableInteger\n",
    "        self.desiredTotal = desiredTotal\n",
    "        self.allUsed = 2 ** maxChoosableInteger - 1\n",
    "        return self.minimax(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(s: str, score: int) -> bool:\n",
    "            '''\n",
    "            Args:\n",
    "                s(str): 当前的整数池, 1表示可选, 0表示不可选\n",
    "                score(int): 当前得分\n",
    "            Returns:\n",
    "                flag(bool): 先手玩家能否胜利\n",
    "            '''\n",
    "            if score >= desiredTotal:\n",
    "                return False\n",
    "            for i in range(len(s)):\n",
    "                if s[i] == '1':\n",
    "                    if not dfs(s[:i] + '0' + s[i+1:], score + i + 1):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "        elif maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal:\n",
    "            return False\n",
    "        else:\n",
    "            return dfs('1' * maxChoosableInteger, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal : return True\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal : return False\n",
    "\n",
    "        dp_win = dict()\n",
    "        dp_lose = dict()\n",
    "\n",
    "        def must_lose(state, total) :\n",
    "            if state in dp_lose : return dp_lose[state]\n",
    "            for i in range(maxChoosableInteger) :\n",
    "                if not state & (1 << i) :\n",
    "                    nextState = state | (1 << i)\n",
    "                    nextTotal = total + i + 1\n",
    "                    if nextTotal >= desiredTotal or not must_win(nextState, nextTotal): \n",
    "                        dp_lose[state] = False\n",
    "                        return False\n",
    "            dp_lose[state] = True\n",
    "            return True\n",
    "        \n",
    "        def must_win(state, total) :\n",
    "            if state in dp_win : return dp_win[state]\n",
    "            for i in range(maxChoosableInteger) :\n",
    "                if not state & (1 << i) :\n",
    "                    nextState = state | (1 << i)\n",
    "                    nextTotal = total + i + 1\n",
    "                    if nextTotal >= desiredTotal or must_lose(nextState, nextTotal): \n",
    "                        dp_win[state] = True\n",
    "                        return True\n",
    "            dp_win[state] = False\n",
    "            return False\n",
    "        return must_win(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(untaken):\n",
    "            remaining=desiredTotal\n",
    "            numsleft=[]\n",
    "            for i in range(1,maxChoosableInteger+1):\n",
    "                if not (1<<i)&untaken:\n",
    "                    remaining-=i\n",
    "                else:\n",
    "                    numsleft.append(i)\n",
    "            if remaining<1:\n",
    "                return True\n",
    "\n",
    "            for i in numsleft:\n",
    "                if not dfs(untaken&(~(1<<i))):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs((1<<maxChoosableInteger)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canIWin(self, maxChoosableInteger, desiredTotal):\n",
    "        \"\"\"\n",
    "        :type maxChoosableInteger: int\n",
    "        :type desiredTotal: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if maxChoosableInteger >= desiredTotal : return True\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal : return False\n",
    "\n",
    "        dp_win = dict()\n",
    "        dp_lose = dict()\n",
    "\n",
    "        # @lru_cache()\n",
    "        def must_lose(state, total) :\n",
    "            if state in dp_lose : return dp_lose[state]\n",
    "            for i in range(maxChoosableInteger) :\n",
    "                if not state & (1 << i) :\n",
    "                    nextState = state | (1 << i)\n",
    "                    nextTotal = total + i + 1\n",
    "                    if nextTotal >= desiredTotal or not must_win(nextState, nextTotal): \n",
    "                        dp_lose[state] = False\n",
    "                        return False\n",
    "            dp_lose[state] = True\n",
    "            return True\n",
    "\n",
    "        # @lru_cache()\n",
    "        def must_win(state, total) :\n",
    "            if state in dp_win : return dp_win[state]\n",
    "            for i in range(maxChoosableInteger) :\n",
    "                if not state & (1 << i) :\n",
    "                    nextState = state | (1 << i)\n",
    "                    nextTotal = total + i + 1\n",
    "                    if nextTotal >= desiredTotal or must_lose(nextState, nextTotal): \n",
    "                        dp_win[state] = True\n",
    "                        return True\n",
    "            dp_win[state] = False\n",
    "            return False\n",
    "        return must_win(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.win_state = set()\n",
    "        self.lose_state = set()\n",
    "\n",
    "    def canUserWin(self, max_int, state, total):\n",
    "        if total <= 0:\n",
    "            return False\n",
    "        if state in self.win_state:\n",
    "            return True\n",
    "        if state in self.lose_state:\n",
    "            return False\n",
    "        for i in range(max_int - 1, -1, -1):\n",
    "            tmp = 1 << i\n",
    "            if tmp & state > 0:\n",
    "                continue\n",
    "            sub = self.canUserWin(max_int, state + tmp, total - i - 1)\n",
    "            if not sub:\n",
    "                self.win_state.add(state)\n",
    "                return True\n",
    "        self.lose_state.add(state)\n",
    "        return False\n",
    "        \n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal <= 0:\n",
    "            return True\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal:\n",
    "            return False\n",
    "        return self.canUserWin(maxChoosableInteger, 0, desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True\n",
    "        if (maxChoosableInteger+1)*maxChoosableInteger/2 < desiredTotal:\n",
    "            return False\n",
    "        \n",
    "        def dfs(use, dp: dict, desiredTotal):\n",
    "            if dp.get(use, None)!=None:\n",
    "                return dp[use]\n",
    "            for i in range(maxChoosableInteger):\n",
    "                cur = 1 << i\n",
    "                if cur&use==0:\n",
    "                    if desiredTotal - i-1 <=0 or not dfs(use|cur, dp, desiredTotal-i-1):\n",
    "                        dp[use] = True\n",
    "                        return True\n",
    "            dp[use] = False\n",
    "            return False\n",
    "\n",
    "        return dfs(0, dict(), desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:\n",
    "            return False\n",
    "        dictionary = {}\n",
    "        return self.dfs(0, 0, maxChoosableInteger, desiredTotal, dictionary)\n",
    "\n",
    "    def dfs(self, state, sum, maxChoosableInteger, desiredTotal, dictionary) -> bool:\n",
    "        # 已经计算过了，直接返回\n",
    "        if state in dictionary.keys():\n",
    "            return dictionary[state]\n",
    "        for x in range(1, maxChoosableInteger + 1):\n",
    "            if not (state & (1 << x)):\n",
    "                # 当前和大于等于desiredTotal，当前玩家获胜\n",
    "                if sum + x >= desiredTotal:\n",
    "                    dictionary[state] = True\n",
    "                    return True\n",
    "\n",
    "                # 移除当前选择值\n",
    "                # 当前玩家选择了x之后，判断对方玩家一定输吗\n",
    "                if not self.dfs(state | (1 << x), sum + x, maxChoosableInteger, desiredTotal, dictionary):\n",
    "                    dictionary[state] = True\n",
    "                    return True\n",
    "\n",
    "        dictionary[state] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "\n",
    "        if sum(range(maxChoosableInteger+1)) < desiredTotal:\n",
    "            return False\n",
    "\n",
    "        A, B = 0, 1\n",
    "        A_WIN = True\n",
    "        B_WIN = False\n",
    "\n",
    "        # 每一位存储是否已经被访问过\n",
    "        used = 0\n",
    "        dp = [[{}, {}] for _ in range(desiredTotal+1)]\n",
    "\n",
    "        def round(turn, used, total):\n",
    "            # 到达结局,\n",
    "            if total <= 0:\n",
    "                return A_WIN if turn == B else B_WIN\n",
    "\n",
    "            result = dp[total][turn].get(used, None)\n",
    "            if result is not None:\n",
    "                return result\n",
    "\n",
    "            for i in range(1, maxChoosableInteger+1):\n",
    "                if used & (1 << i) == 0:\n",
    "                    result = round(1-turn, used | (1 << i),total-i)\n",
    "                    if (turn == A and result == A_WIN) or (turn == B and result == B_WIN):\n",
    "                        break\n",
    "            dp[total][turn][used] = result\n",
    "            return result\n",
    "\n",
    "        return round(A, 0, desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        flg = int('0b' + '1' * maxChoosableInteger, 0)\n",
    "        dp = [{} for x in range(desiredTotal + 1)]\n",
    "        if (1+maxChoosableInteger)*maxChoosableInteger//2 < desiredTotal:\n",
    "            return False\n",
    "\n",
    "        def dfs(res, flgx):\n",
    "            if flgx in dp[res]:\n",
    "                return dp[res][flgx]\n",
    "\n",
    "            for i in range(maxChoosableInteger):\n",
    "                if (flgx >> i & 1) and i + 1 >= res:\n",
    "                    dp[res][flgx] = True\n",
    "                    return True\n",
    "            for i in range(maxChoosableInteger):\n",
    "                if (flgx >> i & 1):\n",
    "                    nflg = flgx & ~(1 << i)\n",
    "                    if dfs(res - i - 1, nflg) is not True:\n",
    "                        dp[res][flgx] = True\n",
    "                        return True\n",
    "            dp[res][flgx] = False\n",
    "            return False\n",
    "\n",
    "        return dfs(desiredTotal, flg)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) // 2 < desiredTotal:\n",
    "            return False\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True\n",
    "        \n",
    "        dp = [None]*(1<<maxChoosableInteger)\n",
    "        def dfs(state, leave):\n",
    "            if dp[state] is not None: \n",
    "                return dp[state]\n",
    "            for i in range(1, maxChoosableInteger+1): # 这里是所有的可能被选的数\n",
    "                choose = 1<<(i-1)\n",
    "                if state & choose:\n",
    "                    continue\n",
    "                if i>=leave or not dfs(state | choose, leave - i):\n",
    "                    dp[state] = True\n",
    "                    return True \n",
    "            dp[state] = False \n",
    "            return False \n",
    "        return dfs(0, desiredTotal)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger*(maxChoosableInteger+1)*0.5<desiredTotal: return False\n",
    "        self.memo = {}\n",
    "        def judge(ava,tar,player):\n",
    "            if (ava,tar,player) not in self.memo:\n",
    "                if not ava: self.memo[(ava,tar,player)] = False\n",
    "                elif max(ava)>=tar: self.memo[(ava,tar,player)] = True\n",
    "                else:\n",
    "                    for choice in ava:\n",
    "                        flag = 1\n",
    "                        if not judge(ava-set([choice]),tar-choice,1-player):\n",
    "                            self.memo[(ava,tar,player)] = True\n",
    "                            flag = 0\n",
    "                            break\n",
    "                        if flag: self.memo[(ava,tar,player)] = False\n",
    "\n",
    "            return self.memo[(ava,tar,player)]\n",
    "        \n",
    "        return judge(frozenset(list(range(1,maxChoosableInteger+1))),desiredTotal,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        ma, total = maxChoosableInteger, desiredTotal\n",
    "        if (ma + 1) * ma // 2 < total:\n",
    "            return False\n",
    "        cache = [-1] * (1 << ma)\n",
    "\n",
    "        def dfs(msk, t):\n",
    "            if cache[msk] != -1:\n",
    "                return bool(cache[msk])\n",
    "            for i in range(ma):\n",
    "                if (1 << i) & msk == 0 and (t + i + 1 >= total or not dfs((1 << i) ^ msk, t + i + 1)):\n",
    "                    cache[msk] = 1\n",
    "                    return True\n",
    "            cache[msk] = 0\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:\n",
    "            return False\n",
    "        dp = [False] * (1 << maxChoosableInteger)\n",
    "        def dfs(usedNumbers: int, currentTotal: int) -> bool:\n",
    "            if dp[usedNumbers]:\n",
    "                return dp[usedNumbers]\n",
    "            for i in range(maxChoosableInteger):\n",
    "                if (usedNumbers >> i) & 1 == 0:\n",
    "                    if currentTotal + i + 1 >= desiredTotal or not dfs(usedNumbers | (1 << i), currentTotal + i + 1):\n",
    "                        dp[usedNumbers] = True\n",
    "                        return True\n",
    "            dp[usedNumbers] = False\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\r\n",
    "        # dfs深度搜索\r\n",
    "        used_num_dic = {}\r\n",
    "        used_num = 0\r\n",
    "        if (1+maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:\r\n",
    "            return False\r\n",
    "        def dfs(used_num, cur_val):\r\n",
    "            if used_num in used_num_dic:\r\n",
    "                return used_num_dic[used_num]\r\n",
    "            for i in range(maxChoosableInteger):\r\n",
    "                if (used_num >> i) & 1 != 0:\r\n",
    "                    continue\r\n",
    "                if cur_val+i+1 >= desiredTotal or not dfs((used_num | 1 << i), cur_val+i+1):\r\n",
    "                    # used_num[i] = \"0\"\r\n",
    "                    used_num_dic[used_num] = True\r\n",
    "                    return True\r\n",
    "                # if not dfs(used_num, cur_val+i+1):\r\n",
    "                    # used_num_dic[used_num] = True\r\n",
    "                    # used_num[i] = \"0\"\r\n",
    "                    # return True\r\n",
    "                # used_num_dic[used_num] = False\r\n",
    "                # used_num[i] = \"0\"\r\n",
    "            # used_num_dic[\"\".join(used_num)] = False\r\n",
    "            return False\r\n",
    "        return dfs(used_num, 0)\r\n",
    "print(Solution().canIWin(10, 40))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "#         if desiredTotal == 0:\n",
    "#             return True\n",
    "#\n",
    "#         if sum(range(1, maxChoosableInteger+1)) < desiredTotal:\n",
    "#             return False\n",
    "#\n",
    "#         can_win = dict()\n",
    "#\n",
    "#         def dfs(available, current_sum):\n",
    "#             # 整数available编码当前可以使用的数字\n",
    "#             # 比如0b1111011表示maxChoosableInteger=7，当前数字3已经被取出\n",
    "#             # 该函数计算只剩下这些数时，先手方能否获胜\n",
    "#             # 如果以前已经考虑过这种情形，结束\n",
    "#             if can_win.get(available) is not None:\n",
    "#                 return\n",
    "#\n",
    "#             if current_sum >= desiredTotal:\n",
    "#                 # 前面一个选择数字的人已经爆掉了目标数字\n",
    "#                 can_win[available] = False\n",
    "#                 return\n",
    "#\n",
    "#             for i in range(maxChoosableInteger):\n",
    "#                 if (available & (1 << i)):\n",
    "#                     # 这个数字可以使用，考虑一下\n",
    "#                     available_after = available ^ (1 << i)\n",
    "#                     dfs(available_after, current_sum + i + 1)\n",
    "#\n",
    "#                     if not can_win[available_after]:\n",
    "#                         # 取出这个数字后，后手方没有办法获胜\n",
    "#                         # 所以当前先手方有必胜法\n",
    "#                         can_win[available] = True\n",
    "#                         return\n",
    "#             can_win[available] = False\n",
    "#\n",
    "#         dfs(sum([1 << i for i in range(maxChoosableInteger)]), 0)\n",
    "#         return can_win[sum([1 << i for i in range(maxChoosableInteger)])]\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def recursion(self, state: int, desiredTotal: int):\n",
    "        if (state, desiredTotal) in self.memory:\n",
    "            return self.memory[state, desiredTotal]\n",
    "\n",
    "        min_num = None\n",
    "        max_num = None\n",
    "        for i in range(self.maxChoosableInteger):\n",
    "            if state & (1 << i):\n",
    "                if min_num is None:\n",
    "                    min_num = i + 1\n",
    "                max_num = i + 1\n",
    "\n",
    "        if max_num >= desiredTotal:\n",
    "            self.memory[state, desiredTotal] = True\n",
    "            return True\n",
    "\n",
    "        if min_num + max_num >= desiredTotal:\n",
    "            # if the first player take any number except for the maximal one,\n",
    "            #   the second player can take the maximal number and win;\n",
    "            # if the first player take the maximal one, the second player takes any other left\n",
    "            self.memory[state, desiredTotal] = False\n",
    "            return False\n",
    "\n",
    "        for i in range(self.maxChoosableInteger):\n",
    "            if state & (1 << i):\n",
    "                if not self.recursion(state ^ (1 << i), desiredTotal - (i+1)):\n",
    "                    # the first player try to pick the number i+1\n",
    "                    #   if the second play is not guaranteed to win, then the first player wins\n",
    "                    self.memory[state, desiredTotal] = True\n",
    "                    return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (s := sum(range(1, maxChoosableInteger+1))) < desiredTotal:\n",
    "            return False\n",
    "        elif s == desiredTotal:\n",
    "            return maxChoosableInteger%2 == 1\n",
    "\n",
    "        # memory[01101101, j] = canIWin({1, 3, 4, 6, 7}, j)\n",
    "        self.maxChoosableInteger = maxChoosableInteger\n",
    "        self.memory = dict()\n",
    "        return self.recursion(sum([1 << i for i in range(maxChoosableInteger)]), desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger*(maxChoosableInteger+1)<desiredTotal*2:\n",
    "            return False\n",
    "        mark= {}\n",
    "        key = [\"0\"]*maxChoosableInteger\n",
    "        return self.dfs(key,desiredTotal,mark)\n",
    "    \n",
    "    def dfs(self,key,desiredTotal,mark):\n",
    "        key_s = ''.join(key)\n",
    "        if key_s in mark:\n",
    "            return mark[key_s]\n",
    "        if desiredTotal<=0:\n",
    "            return True\n",
    "        for i in range(len(key)):\n",
    "            if key[i]=='0':\n",
    "                key[i]='1'\n",
    "                if desiredTotal-i-1<=0 or not self.dfs(key,desiredTotal-i-1,mark):\n",
    "                    mark[key_s] = True\n",
    "                    key[i]='0'\n",
    "                    return True\n",
    "                key[i]='0'\n",
    "        mark[key_s] = False\n",
    "        return mark[key_s]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        memory = [-1 for x in range(1<< maxChoosableInteger)]\n",
    "        def dfs(used, sum):\n",
    "            if memory[used] != -1:\n",
    "                return memory[used] == 1 \n",
    "            for i in range(maxChoosableInteger):\n",
    "                if (used >> (i)) & 1 == 1:\n",
    "                    continue \n",
    "                if sum+i+1 >= desiredTotal or not dfs(used | (1 << (i)), sum+i+1):\n",
    "                    memory[used] = 1 \n",
    "                    return True \n",
    "            memory[used] = 0 \n",
    "            return False \n",
    "        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        return self.solution(maxChoosableInteger,desiredTotal)\n",
    "    def solution(self, maxRange:int,total:int) -> bool:\n",
    "\t    memo = {}\n",
    "\t    curS,curU = 0,0\n",
    "\t    def dp() -> int:\n",
    "\t    \tnonlocal curS,curU #\n",
    "\t    \tif memo.get(curS<<maxRange|curU):\n",
    "\t    \t\treturn memo[curS<<maxRange|curU]\n",
    "\t    \tres = False\n",
    "\t    \tfor i in range(1,maxRange+1):\n",
    "\t    \t\tif curU >> (i-1) & 1 == 1:\n",
    "\t    \t\t\tcontinue\n",
    "\t    \t\tcurU |= 1 << (i-1)\n",
    "\t    \t\tcurS += i\n",
    "\t    \t\tif curS >= total or not dp():\n",
    "\t    \t\t\tcurU ^= 1 << (i-1)\n",
    "\t    \t\t\tcurS -= i\n",
    "\t    \t\t\tres = True\n",
    "\t    \t\t\tbreak\n",
    "\t    \t\tcurU ^= 1 << (i-1)\n",
    "\t    \t\tcurS -= i\n",
    "\t    \tmemo[curS<<maxRange|curU] = res\n",
    "\t    \treturn res\n",
    "\t    return ((1 + maxRange) * maxRange // 2) >= total and dp()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {}\n",
    "\n",
    "    def helper(self, max_num, used, total):\n",
    "        i = max_num \n",
    "        while i >= total:\n",
    "            if not used[i-1]:\n",
    "                return True\n",
    "            i -= 1\n",
    "\n",
    "        bool_I_can_wing = False\n",
    "        for i in range(1, max_num):\n",
    "            if used[i-1]:\n",
    "                continue\n",
    "            used[i-1] = True\n",
    "\n",
    "            key = (str(used), total-i)\n",
    "\n",
    "            if key not in self.cache:\n",
    "                self.cache[key] = self.helper(max_num, used, total - i)\n",
    "\n",
    "            used[i-1] = False\n",
    "\n",
    "            if not self.cache[key]:\n",
    "                bool_I_can_wing = True\n",
    "                break\n",
    "\n",
    "        return bool_I_can_wing\n",
    "            \n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        '''\n",
    "        1 to maxChoosableInteger\n",
    "        sum = desiredTotal\n",
    "        '''\n",
    "        if (1+maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "\n",
    "        used = [False] * maxChoosableInteger\n",
    "        \n",
    "        ret = self.helper(maxChoosableInteger, used, desiredTotal)\n",
    "        #print(self.cache)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 策略：如果剩余的最大值取了可以使得累计和>=desiredTotal，则直接取最大值，\n",
    "# 当desired大于maxChoose的时候，先手必须选择小于desire-maxChoose的值才能不输\n",
    "# 遍历先手的每种选择，如果有一种选择导致的结果是赢，则返回True，否则返回FalseFalse\n",
    "# 记忆优化防止重复计算\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal:\n",
    "            return False\n",
    "        memory = {}\n",
    "        \n",
    "        return self.dfs(0,maxChoosableInteger,desiredTotal,memory)\n",
    "\n",
    "    \n",
    "        \n",
    "\n",
    "    def dfs(self,used,maxChoosableInteger,desiredTotal,memory):\n",
    "        if (used,desiredTotal) in memory:\n",
    "            return memory[(used,desiredTotal)]\n",
    "\n",
    "        for i in range(maxChoosableInteger):\n",
    "            if (used >> i) & 1 == 0:\n",
    "                val = i+1\n",
    "                 \n",
    "                if desiredTotal - val <= 0:\n",
    "                    memory[(used,desiredTotal)] = True \n",
    "                    return True \n",
    "                else:\n",
    "                    used += 2**i\n",
    "                    x = self.dfs(used,maxChoosableInteger,desiredTotal - val,memory)\n",
    "                    used -= 2**i\n",
    "                    if not x:\n",
    "                        memory[(used,desiredTotal)] = True \n",
    "                        return True \n",
    "        memory[(used,desiredTotal)] = False \n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        @cache\n",
    "        def f(state):\n",
    "            now=sum([i for i in range(1,21) if (state>>i)&1])\n",
    "            res=False\n",
    "            for i in range(1,maxChoosableInteger+1):\n",
    "                if state&(1<<i)==0:\n",
    "                    if now+i>=desiredTotal:\n",
    "                        return True\n",
    "                    res|= not f(state|(1<<i))\n",
    "                    if res:\n",
    "                        return True\n",
    "                \n",
    "            return False\n",
    "        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and f(0)\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        total = (1 + maxChoosableInteger) / 2 * maxChoosableInteger\n",
    "        if total < desiredTotal: return False\n",
    "\n",
    "        @cache\n",
    "        def fun(s):\n",
    "            pre = sum(i for i in range(1, maxChoosableInteger + 1) if (s >> i) & 1 == 1)\n",
    "\n",
    "            res = False\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                if (s >> i) & 1 == 0:\n",
    "                    if pre + i >= desiredTotal:\n",
    "                        return True\n",
    "                    else:\n",
    "                        res |= not fun(s | (1 << i))\n",
    "                        if res: break\n",
    "            return res\n",
    "\n",
    "        return fun(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef canIWin(self, maxChoosableInteger, desiredTotal):\n",
    "\t\tif maxChoosableInteger * (maxChoosableInteger + 1) < desiredTotal * 2:\n",
    "\t\t\treturn False\n",
    "\t\tself.win = set()\n",
    "\t\tself.loss = set()\n",
    "\t\treturn self.recall(tuple(range(1, maxChoosableInteger + 1)), desiredTotal)\n",
    "\t\t#print(self.win, self.loss)\n",
    "\t\n",
    "\tdef recall(self, t, k):\n",
    "\t\tif k <= t[-1]:\n",
    "\t\t\tself.win.add(t)\n",
    "\t\t\treturn True\n",
    "\t\tfor i in range(len(t)):\n",
    "\t\t\tnextT = t[:i] + t[i + 1:]\n",
    "\t\t\tif nextT in self.win:\n",
    "\t\t\t\tcontinue\n",
    "\t\t\tif nextT in self.loss or self.recall(t[:i] + t[i + 1:], k - t[i]) == False:\n",
    "\t\t\t\tself.win.add(t)\n",
    "\t\t\t\treturn True\n",
    "\t\tself.loss.add(t)\n",
    "\t\treturn False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal:\n",
    "            return False\n",
    "        tag = {}\n",
    "        def dfs(vis, cur):\n",
    "            if vis in tag:\n",
    "                return tag[vis]\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                if (1 << i) & vis == 0:\n",
    "                    if cur + i >= desiredTotal:\n",
    "                        tag[vis] = True\n",
    "                        return True\n",
    "                    if not dfs(vis | (1 << i), cur + i):\n",
    "                        tag[vis] = True\n",
    "                        return True\n",
    "            tag[vis] = False\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "class Solution():\n",
    "    def canIWin(self, maxChoosableInteger, desiredTotal):\n",
    "        usable = [x for x in range(1,maxChoosableInteger +1)]\n",
    "        if (1+ maxChoosableInteger) * maxChoosableInteger <= desiredTotal:\n",
    "            return False\n",
    "        else:\n",
    "            return self.hint(maxChoosableInteger,desiredTotal,usable,{},0)\n",
    "        \n",
    "    def hint(self,maxChoosbleInt,desiredTotal,usable,cache,already):\n",
    "        if len(usable) == 0:\n",
    "            return False\n",
    "        else:\n",
    "            state = tuple(usable)\n",
    "            if state in cache:\n",
    "                return cache[state]\n",
    "            else:\n",
    "                cache[state] = False\n",
    "                if max(usable) + already >= desiredTotal:\n",
    "                    cache[state] = True\n",
    "                elif len(usable) >1 and max(usable) + already >= desiredTotal:\n",
    "                    cache[state] = False\n",
    "                else:\n",
    "                    for x in usable:\n",
    "                        newstate = [y for y in usable if y!= x]\n",
    "                        if not self.hint(maxChoosbleInt,desiredTotal,newstate,cache,already + x):\n",
    "                            cache[state] = True\n",
    "                            break\n",
    "                return cache[state]   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def recursive(max0, total, table, pick):\n",
    "    left = list(set(list(range(1,max0+1)))-set(pick))\n",
    "    left.sort()\n",
    "    total1 = total - sum(pick)\n",
    "    if left[-1] >= total1:\n",
    "        table[tuple(pick)] = True\n",
    "        return True\n",
    "    if left[0] + left[-1] >= total1:\n",
    "        table[tuple(pick)] = False\n",
    "        return False\n",
    "    for v in left:\n",
    "        pick1 = pick + [v]\n",
    "        pick1.sort()\n",
    "        tmp = table.get(tuple(pick1))\n",
    "        if tmp is None:\n",
    "            tmp = recursive(max0, total, table, pick1)\n",
    "        if tmp == False:\n",
    "            table[tuple(pick)] = True\n",
    "            return True\n",
    "    table[tuple(pick)] = False\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        delta = (1+maxChoosableInteger)*maxChoosableInteger - 2*desiredTotal\n",
    "        if delta < 0:\n",
    "            return False\n",
    "        if delta == 0:\n",
    "            return bool(maxChoosableInteger%2)\n",
    "        if desiredTotal % (2+maxChoosableInteger) == 1:\n",
    "            return True\n",
    "        if desiredTotal % maxChoosableInteger == 0 and maxChoosableInteger%2 == 1:\n",
    "            return True\n",
    "        if maxChoosableInteger%2 == 1 and desiredTotal%(maxChoosableInteger+1)==maxChoosableInteger//2+1:\n",
    "            return True\n",
    "        table = dict()\n",
    "        return recursive(maxChoosableInteger, desiredTotal, table, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (maxChoosableInteger+1)*maxChoosableInteger//2 < desiredTotal:\n",
    "            return False\n",
    "        if not desiredTotal:\n",
    "            return True\n",
    "        M = 1 << maxChoosableInteger\n",
    "        dp = [[-1]*2 for _ in range(M)]\n",
    "\n",
    "        def dfs(state, total, k):\n",
    "            player = k % 2\n",
    "            if dp[state][player] != -1:\n",
    "                return dp[state][player]\n",
    "            if total >= desiredTotal:\n",
    "                dp[state][player] = not player\n",
    "                return dp[state][player]\n",
    "            dp[state][player] = not player\n",
    "            for i in range(maxChoosableInteger):\n",
    "                num = i + 1\n",
    "                if state >> i & 1:\n",
    "                    continue\n",
    "                next_state = state | 1 << i\n",
    "                next_total = num + total\n",
    "                next_result = dfs(next_state, next_total, k+1)\n",
    "                if next_result == player:\n",
    "                    dp[state][player] = player\n",
    "                    break\n",
    "            return dp[state][player]\n",
    "\n",
    "        result = dfs(0, 0, 0)\n",
    "        return result == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:\n",
    "            return False\n",
    "\n",
    "        self.memo = {}\n",
    "\n",
    "        def dfs(curr, desiredTotal):\n",
    "            hash = str(curr)\n",
    "            if hash in self.memo:\n",
    "                return self.memo[hash]\n",
    "\n",
    "            if curr[-1] >= desiredTotal:\n",
    "                return True\n",
    "\n",
    "            for i in range(len(curr)):\n",
    "                if not dfs(curr[:i] + curr[i+1:], desiredTotal-curr[i]):\n",
    "                    self.memo[hash] = True\n",
    "                    return True\n",
    "\n",
    "            return False           \n",
    "\n",
    "\n",
    "        return dfs(list(range(1, maxChoosableInteger+1)), desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger*(1+maxChoosableInteger)//2 < desiredTotal:\n",
    "            return False\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True\n",
    "\n",
    "        dp = {}\n",
    "        dp2 = {}\n",
    "        def play1(nums, target):\n",
    "            key = tuple(nums)\n",
    "            if key in dp:\n",
    "                return dp[key]\n",
    "            if target <= nums[-1]:\n",
    "                dp[key] = True\n",
    "                return True\n",
    "            for i, n in enumerate(nums):\n",
    "                if not play2(nums[:i]+nums[i+1:], target-n):\n",
    "                    dp[key] = True\n",
    "                    return True\n",
    "            dp[key] = False\n",
    "            return False\n",
    "        \n",
    "        def play2(nums, target):\n",
    "            key = tuple(nums)\n",
    "            if key in dp2:\n",
    "                return dp2[key]\n",
    "            if target <= nums[-1]:\n",
    "                dp2[key] = True\n",
    "                return True\n",
    "            for i, n in enumerate(nums):\n",
    "                if not play1(nums[:i]+nums[i+1:], target-n):\n",
    "                    dp2[key] = True\n",
    "                    return True\n",
    "            dp2[key] = False\n",
    "            return False\n",
    "        \n",
    "        return play1(list(range(1, maxChoosableInteger+1)), desiredTotal)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        dp = dict()\n",
    "        def rrc(total,chos):\n",
    "        #     print(total,chos)\n",
    "            if sum(chos)<total:\n",
    "                return False\n",
    "            if (total,chos) in dp:\n",
    "                return dp[(total,chos)]\n",
    "            chosl = list(chos)\n",
    "            if total<=chosl[-1]:\n",
    "                dp[(total,chos)]=True\n",
    "                return True\n",
    "            else:\n",
    "                if chosl[-1]+chosl[0]>=total:\n",
    "                    dp[(total,chos)]=False\n",
    "                    return False\n",
    "                else:\n",
    "                    if chosl[-1]+chosl[0]+chosl[1]>=total:\n",
    "                        dp[(total,chos)]=True\n",
    "                        return True\n",
    "                    else:\n",
    "                        res = False\n",
    "                        for i in range(len(chosl)):\n",
    "                            \n",
    "                            cur = chosl[i]\n",
    "                            chos_c = chosl.copy()\n",
    "                            chos_c.remove(cur)\n",
    "                            \n",
    "                            r = not rrc(total-cur, tuple(chos_c))\n",
    "                            if r==True:\n",
    "                                dp[(total,chos)] =r \n",
    "                                return r\n",
    "                        \n",
    "                        return res\n",
    "        return rrc(desiredTotal,tuple(range(1,maxChoosableInteger+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        iter_index = list(reversed(range(maxChoosableInteger)))\n",
    "        cache =dict()\n",
    "        def impl(bitmap,total):\n",
    "            key = bitmap << 32 + total\n",
    "            if key in cache:\n",
    "                return cache[key]\n",
    "            for i in iter_index:\n",
    "                index = 1 << i\n",
    "                if bitmap & index:\n",
    "                    if i + 1 >= total:\n",
    "                        return True\n",
    "                    if not impl(bitmap ^ index,total - i - 1):\n",
    "                        cache[key] = True\n",
    "                        return True\n",
    "            cache[key] = False\n",
    "            return False\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        init_bitmap = 0\n",
    "        for i in range(maxChoosableInteger):\n",
    "            init_bitmap ^= 1 << i\n",
    "        return impl(init_bitmap,desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin2(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal: return True\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: return False\n",
    "\n",
    "        def dfs(state, desiredTotal, dp):\n",
    "            if dp[state] != None:\n",
    "                return dp[state]\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                cur = 1 << (i - 1)\n",
    "                if cur & state != 0:\n",
    "                    continue\n",
    "                \n",
    "                if i >= desiredTotal or not dfs(cur | state, desiredTotal - i, dp):\n",
    "                    dp[state] = True\n",
    "                    return True\n",
    "            dp[state] = False\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, desiredTotal, [None] * (1 << maxChoosableInteger))\n",
    "\n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        dp = dict()\n",
    "        def rrc(total,chos):\n",
    "        #     print(total,chos)\n",
    "            if sum(chos)<total:\n",
    "                return False\n",
    "            if (total,chos) in dp:\n",
    "                return dp[(total,chos)]\n",
    "            chosl = list(chos)\n",
    "      \n",
    "            for i in range(len(chosl)):\n",
    "                \n",
    "                cur = chosl[i]\n",
    "                if cur >= total:\n",
    "                    dp[(total,chos)]=True\n",
    "                    return True\n",
    "                chos_c = chosl.copy()\n",
    "                chos_c.remove(cur)\n",
    "                \n",
    "                r = not rrc(total-cur, tuple(chos_c))\n",
    "                if r==True:\n",
    "                    dp[(total,chos)] =r \n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "        return rrc(desiredTotal,tuple(range(1,maxChoosableInteger+1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        n, t = maxChoosableInteger, desiredTotal\n",
    "        maxMask = (1 << n) - 1\n",
    "        @cache\n",
    "        def maskToInt(mask: int) -> int:\n",
    "            return sum(i + 1 for i in range(n) if mask & 1 << i)\n",
    "\n",
    "        # mask mean already picked number status, at this status, if can final win, return true\n",
    "        @lru_cache(None)\n",
    "        def dfs(mask: int) -> bool:\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1 == 1: continue\n",
    "                if maskToInt(mask) + i + 1 >= t: return True\n",
    "                # this player pick one number\n",
    "                if dfs(mask | (1 << i)) == False: return True\n",
    "            return False\n",
    "\n",
    "        if n * (n + 1) / 2 < t: return False\n",
    "        if t == 0: return True\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if sum(list(range(1,desiredTotal+1))) < desiredTotal:\n",
    "            return False\n",
    "        record = {}\n",
    "        def dfs(to_use,sums,player):\n",
    "            if to_use[-1] >= sums:\n",
    "                if player:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if sum(to_use) < sums:\n",
    "                if player:\n",
    "                    return False \n",
    "                else:\n",
    "                    return True\n",
    "            if len(to_use) == 1 and to_use[-1] < sums:\n",
    "                return False\n",
    "            if (tuple(to_use),sums,player) in record:\n",
    "                return record[(tuple(to_use),sums,player)]\n",
    "            if player:\n",
    "                for i in range(len(to_use)):\n",
    "                    if dfs(to_use[:i]+to_use[i+1:],sums-to_use[i],False):\n",
    "                        record[(tuple(to_use),sums,player)] = True\n",
    "                        return True\n",
    "                record[(tuple(to_use),sums,player)] = False\n",
    "                return False \n",
    "            else:\n",
    "                for i in range(len(to_use)):\n",
    "                    if not dfs(to_use[:i]+to_use[i+1:],sums-to_use[i],True):\n",
    "                        record[(tuple(to_use),sums,player)] = False\n",
    "                        return False\n",
    "                record[(tuple(to_use),sums,player)] = True\n",
    "                return True \n",
    "        return dfs(list(range(1,maxChoosableInteger+1)),desiredTotal,True)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        #动态规划思路\n",
    "        #这里是采用动态规划,达到去重的目的\n",
    "        # 边界判断\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True  # 先手一定赢\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        n = maxChoosableInteger + 1\n",
    "        dp=[0 for i in range(2**(maxChoosableInteger+1))]  #所有的可能性  如10001  10010\n",
    "        def digui(senums,count):\n",
    "            if dp[senums]!=0:\n",
    "                return dp[senums]  #说明走过这条路\n",
    "            for i in range(1,n):\n",
    "                if (1<<i)&senums==0:  #说明没有选取过\n",
    "                    if count+i>=desiredTotal or not digui(senums|(1<<i),count+i): #说明选了之后就赢了\n",
    "                        dp[senums]=True\n",
    "                        return True\n",
    "            dp[senums]=False\n",
    "            return False\n",
    "        return digui(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal<maxChoosableInteger:\n",
    "            return True\n",
    "        if sum([i for i in range(1,maxChoosableInteger+1)])<desiredTotal:\n",
    "            return False\n",
    "        dp=[None]*(1<<(maxChoosableInteger+1))\n",
    "\n",
    "        def dfs(state,t):\n",
    "            if dp[state]!=None:\n",
    "                return dp[state]\n",
    "\n",
    "            for j in range(1,maxChoosableInteger+1):\n",
    "                cur=1<<j\n",
    "                if state&cur!=0:\n",
    "                    continue\n",
    "                if j>=t:\n",
    "                    dp[state]=True\n",
    "                    return True\n",
    "    \n",
    "                if dfs(state|cur,t-j)==False:\n",
    "                    dp[state]=True\n",
    "                    return True\n",
    "            dp[state]=False\n",
    "            return False\n",
    "\n",
    "        return dfs(0,desiredTotal)                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal<maxChoosableInteger:\n",
    "            return True\n",
    " \n",
    "        dp=[None]*(1 << (maxChoosableInteger+1))\n",
    "        if sum([i for i in range(1,maxChoosableInteger+1)])<desiredTotal:\n",
    "            return False\n",
    "       # if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "       #     return False\n",
    "        vis=[0]*(maxChoosableInteger+1)\n",
    "        vis[0]=1\n",
    "        def dfs(state,t):\n",
    "            if dp[state]!=None:\n",
    "                return dp[state]\n",
    "\n",
    "            for i in range(1,maxChoosableInteger+1):\n",
    "                cur=1<<i\n",
    "                if cur&state!=0:\n",
    "                    continue\n",
    "                if i >=t:\n",
    "                    dp[state]=True\n",
    "                    return True\n",
    "                else:\n",
    "                    if dfs(cur|state,t-i)==False:\n",
    "                        dp[state]=True\n",
    "                        return True\n",
    "            dp[state]=False\n",
    "            return False\n",
    "\n",
    "        return dfs(0,desiredTotal)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal>maxChoosableInteger*(maxChoosableInteger+1)//2:\n",
    "            return False\n",
    "        Mark=[0,1]\n",
    "        for i in range(2, maxChoosableInteger+1):\n",
    "            Mark.append(Mark[i-1]*2)\n",
    "        Dict={}\n",
    "        def func(target, state):\n",
    "            key=\"{}\".format(state)+\"_\"+str(target)\n",
    "            if key in Dict:\n",
    "                return Dict[key]\n",
    "            Dict[key]=True\n",
    "            for i in range(1, maxChoosableInteger+1):\n",
    "                if state&Mark[i]==0:\n",
    "                    if target-i<=0:\n",
    "                        return True\n",
    "                    if not func(target-i, state+Mark[i]):\n",
    "                        return True\n",
    "            Dict[key]=False\n",
    "            return False\n",
    "        return func(desiredTotal,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "\n",
    "        if desiredTotal==0:\n",
    "            return True\n",
    "        if sum(list(range(1, maxChoosableInteger+1)))<desiredTotal:\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur_val, candidates):\n",
    "            for c in candidates:\n",
    "                if cur_val + c >= desiredTotal:\n",
    "                    return True\n",
    "            for i in range(len(candidates)):\n",
    "                choosen = candidates[i]\n",
    "                rest = candidates[:i]+candidates[i+1:]\n",
    "                if not dfs(cur_val+choosen, rest):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "\n",
    "        return dfs(0, tuple(list(range(1, maxChoosableInteger+1))))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        \"\"\" 博弈DP  \n",
    "        if my opponent is not win then I'll win \n",
    "        \"\"\"\n",
    "\n",
    "        # @functools.lru_cache(None)\n",
    "        # def dfs(currRewards, left_numbers):\n",
    "        #     # my turn, no left whole number to choose \n",
    "        #     if not left_numbers:\n",
    "        #         return False \n",
    "\n",
    "        #     left_numbers = list(left_numbers)\n",
    "        #     if desiredTotal - max(left_numbers) <= currRewards:\n",
    "        #         return True \n",
    "\n",
    "        #     # my turn, choose the largest number can win\n",
    "        #     for i in left_numbers:\n",
    "        #         if desiredTotal - i <= currRewards:\n",
    "        #             return True \n",
    "        #         left_numbers_copy = [j for j in left_numbers]\n",
    "        #         left_numbers_copy.remove(i)\n",
    "        #         if not dfs(currRewards+i, tuple(left_numbers_copy)):\n",
    "        #             return True \n",
    "\n",
    "        #     return False \n",
    "\n",
    "        # left_numbers = []\n",
    "        # for i in range(1, maxChoosableInteger+1):\n",
    "        #     left_numbers.append(i)\n",
    "\n",
    "        # return dfs(0, tuple(left_numbers))\n",
    "\n",
    "        # early pruning \n",
    "        if (1+maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:\n",
    "            return False \n",
    "\n",
    "        if desiredTotal < maxChoosableInteger:\n",
    "            return True\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(choosable_list, choosed_sum):\n",
    "            if not choosable_list:\n",
    "                return False \n",
    "\n",
    "            #遍历公共数据池中的数据\n",
    "            choosable_list = list(choosable_list)\n",
    "\n",
    "            for x in choosable_list:\n",
    "                #如果选了x之后已选数据池之和大于desiredTotal\n",
    "                if choosed_sum+x>=desiredTotal:\n",
    "                    return True\n",
    "                #备份一个choosable_list\n",
    "                chose_copy = [item for item in choosable_list]\n",
    "                chose_copy.remove(x)\n",
    "                #当前玩家选择x之后，对手玩家是否稳赢的判断，如果稳输则当前玩家赢\n",
    "                if not dfs(tuple(chose_copy), choosed_sum+x):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        choosable_list=[i+1 for i in range(maxChoosableInteger)]\n",
    "        return dfs(tuple(choosable_list), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "    @lru_cache(maxsize=None)\n",
    "    def search(self,statu:int,cuto:int) -> bool:\n",
    "        for i in range(1,self.max+1):\n",
    "            if not (statu>>i)&1:\n",
    "                new_st=statu+(1<<i)\n",
    "                if cuto+i>=self.de:\n",
    "                    return True\n",
    "                else:\n",
    "                    if not self.search(new_st,cuto+i):\n",
    "                        return True\n",
    "        return False\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        self.max=maxChoosableInteger\n",
    "        self.de=desiredTotal\n",
    "        sum=self.max*(self.max+1)/2\n",
    "        if sum<self.de:\n",
    "            return False\n",
    "        return self.search(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        cache =dict()\n",
    "        def impl(bitmap,total):\n",
    "            if (bitmap,total) in cache:\n",
    "                return cache[(bitmap,total)]\n",
    "            for i in range(maxChoosableInteger):\n",
    "                index = 1 << i\n",
    "                if (bitmap & index) > 0:\n",
    "                    if i + 1 >= total:\n",
    "                        return True\n",
    "                    if not impl(bitmap ^ index,total - i - 1):\n",
    "                        cache[(bitmap,total)] = True\n",
    "                        return True\n",
    "            cache[(bitmap,total)] = False\n",
    "            return False\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        init_bitmap = 0\n",
    "        for i in range(maxChoosableInteger):\n",
    "            init_bitmap ^= 1 << i\n",
    "        return impl(init_bitmap,desiredTotal)\n",
    "\n",
    "\n",
    "# def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "#         bitmap = 1\n",
    "#         for i in range(maxChoosableInteger-1):\n",
    "#             bitmap = bitmap << 1 + 1\n",
    "#         print(bitmap)\n",
    "#         def impl(choose,total):\n",
    "#             for i in range(len(choose)):\n",
    "#                     next_choose = choose.copy()\n",
    "#                     value = next_choose.pop(i)\n",
    "#                     if value >= total:\n",
    "#                         return True\n",
    "#                     if not impl(next_choose,total - value):\n",
    "#                         return True\n",
    "#             return False\n",
    "#         return impl(list(range(1,maxChoosableInteger+1)),desiredTotal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        sums = (1+maxChoosableInteger)*maxChoosableInteger // 2\n",
    "        if sums < desiredTotal:\n",
    "            return False\n",
    "        if maxChoosableInteger >= desiredTotal:\n",
    "            return True\n",
    "        if sums == desiredTotal:\n",
    "            return maxChoosableInteger&1 == 1\n",
    "\n",
    "        dic = {}\n",
    "        def isWin(nums, tmp):\n",
    "            if nums[-1] >= tmp:\n",
    "                return True\n",
    "            seenums = tuple(nums)\n",
    "            if seenums in dic:\n",
    "                return dic[seenums]\n",
    "            for i,num in enumerate(nums):\n",
    "                if not isWin(nums[:i]+nums[i+1:], tmp-num):\n",
    "                    dic[seenums] = True\n",
    "                    return True\n",
    "            dic[seenums] = False\n",
    "            return False\n",
    "        return isWin(list(range(1, maxChoosableInteger+1)), desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        sum_ = (1 + maxChoosableInteger) * maxChoosableInteger // 2 #首项+末项 求和公式\n",
    "        if sum_ < desiredTotal: # 都不能赢\n",
    "            return False\n",
    "        if maxChoosableInteger >= desiredTotal: \n",
    "            return True   #直接取最大\n",
    "        if sum_ == desiredTotal: # 等于desired时候看奇数个还是偶数个，奇数个先手赢\n",
    "            return True if maxChoosableInteger % 2 == 1 else False\n",
    "        \n",
    "        hashmap = {}\n",
    "        def isWin(nums, temp):\n",
    "            if nums[-1] >= temp:\n",
    "                return True\n",
    "            seen = tuple(nums)\n",
    "            if seen in hashmap:\n",
    "                return hashmap[seen]\n",
    "            for i, num in enumerate(nums):\n",
    "                if not isWin(nums[:i] + nums[i + 1:], temp - num):\n",
    "                    hashmap[seen] = True\n",
    "                    return True\n",
    "            hashmap[seen] = False\n",
    "            return False\n",
    "        return isWin(list(range(1, maxChoosableInteger + 1)), desiredTotal)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:     \n",
    "        sc=(1+maxChoosableInteger)*maxChoosableInteger//2\n",
    "        if sc<desiredTotal:\n",
    "            return False\n",
    "        if sc==desiredTotal:\n",
    "            return maxChoosableInteger%2==1 \n",
    "    \n",
    "        memo=defaultdict(bool)\n",
    "        \n",
    "        def canwin(leftnum:int,total:int)->bool:\n",
    "            if (leftnum,total) not in memo:\n",
    "                win=False\n",
    "                if total==0:\n",
    "                    win=True\n",
    "                else:                        \n",
    "                    for i in range(maxChoosableInteger):\n",
    "                        pick=1<<i\n",
    "                        if (pick&leftnum)==pick:\n",
    "                            if i+1>=total:\n",
    "                                win=True\n",
    "                                break\n",
    "                    if not win:\n",
    "                        for i in range(maxChoosableInteger):\n",
    "                            pick=1<<i \n",
    "                            if (pick&leftnum)==pick:\n",
    "                                if not canwin(pick^leftnum,total-i-1):    \n",
    "                                    win=True\n",
    "                                    break\n",
    "                memo[(leftnum,total)]=win            \n",
    "            return memo[(leftnum,total)]\n",
    "        return canwin((1<<maxChoosableInteger)-1,desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        def canIWinHelp(cadinateNums:List[int] , desiredTotal: int , memDic:dict[tuple,bool]) -> bool:\n",
    "            memRes = memDic.get(tuple(cadinateNums))\n",
    "            if memRes:\n",
    "                return memRes\n",
    "            if desiredTotal <= 0:\n",
    "                return False\n",
    "            result = False\n",
    "            for i in range(0,len(cadinateNums)):\n",
    "                if cadinateNums[i] == 0:\n",
    "                    continue\n",
    "                tmp = cadinateNums[i]\n",
    "                cadinateNums[i] = 0\n",
    "                result |= not canIWinHelp(cadinateNums , desiredTotal - tmp , memDic )\n",
    "                cadinateNums[i] = tmp\n",
    "                if result:\n",
    "                    memDic[tuple(cadinateNums)] = result\n",
    "                    return result\n",
    "            memDic[tuple(cadinateNums) ] = result\n",
    "            return result\n",
    "\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal: \n",
    "            return False\n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "        return canIWinHelp([num for num in range(1 , maxChoosableInteger + 1)],desiredTotal,{})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        seen = {}\n",
    "\n",
    "        def canWin(choices, remainder):\n",
    "            if choices[-1] >= remainder:\n",
    "                return True\n",
    "            # keep track of all the values, if we have visited this before we are just going to return it\n",
    "            selected = tuple(choices)\n",
    "            if selected in seen:\n",
    "                return seen[selected]\n",
    "            # your opponent needs to lose for you to win\n",
    "            for i in range(len(choices)):\n",
    "                if not canWin(choices[:i] + choices[i+1:], remainder - choices[i]):\n",
    "                    seen[selected] = True\n",
    "                    return True\n",
    "\n",
    "            # if all have gone through, we know we have lost the game\n",
    "            seen[selected] = False\n",
    "            return False\n",
    "\n",
    "        totalSum = (maxChoosableInteger + 1) * maxChoosableInteger / 2\n",
    "\n",
    "        # check if we can actually play the game, else return false\n",
    "        if totalSum < desiredTotal:\n",
    "            return False\n",
    "        # it's a matter of whether you have an odd or even number\n",
    "        if totalSum == desiredTotal:\n",
    "            return maxChoosableInteger % 2 == 1\n",
    "\n",
    "        choice = list(range(1, maxChoosableInteger + 1))\n",
    "        return canWin(choice, desiredTotal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''暴力\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "    @lru_cache(maxsize=None)\n",
    "    def search(self,statu:int,cuto:int) -> bool:\n",
    "        for i in range(1,self.max+1):\n",
    "            if not (statu>>i)&1:\n",
    "                new_st=statu+(1<<i)\n",
    "                if cuto+i>=self.de:\n",
    "                    return True\n",
    "                else:\n",
    "                    if not self.search(new_st,cuto+i):\n",
    "                        return True\n",
    "        return False\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        self.max=maxChoosableInteger\n",
    "        self.de=desiredTotal\n",
    "        sum=self.max*(self.max+1)/2\n",
    "        if sum<self.de:\n",
    "            return False\n",
    "        return self.search(0,0)'''\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "    @lru_cache(maxsize=None)\n",
    "    def search(self,statu:int,cuto:int,tim:int) -> int:\n",
    "        if statu==self.alll:\n",
    "            return 0\n",
    "        if tim==0:\n",
    "            tim=1\n",
    "            value=-inf\n",
    "            for i in range(1,self.max+1):\n",
    "                if not (statu>>i)&1:\n",
    "                    new_st=statu+(1<<i)\n",
    "                    if cuto+i>=self.de:\n",
    "                        return -1\n",
    "                    value=max(value,self.search(new_st,cuto+i,tim))\n",
    "                    if value==-1:\n",
    "                        return -1\n",
    "        else:\n",
    "            tim=0\n",
    "            value=inf\n",
    "            for i in range(1,self.max+1):\n",
    "                if not (statu>>i)&1:\n",
    "                    new_st=statu+(1<<i)\n",
    "                    if cuto+i>=self.de:\n",
    "                        return -2\n",
    "                    value=min(value,self.search(new_st,cuto+i,tim))\n",
    "                    if value==-2:\n",
    "                        return -2\n",
    "        return value\n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        self.max=maxChoosableInteger\n",
    "        self.de=desiredTotal\n",
    "        sum=self.max*(self.max+1)/2\n",
    "        self.alll=0\n",
    "        for i in range(1,self.max+1):\n",
    "            self.alll+=1<<i\n",
    "        if sum<self.de:\n",
    "            return False\n",
    "        k=self.search(0,0,0)\n",
    "        if k==-1:\n",
    "            return True\n",
    "        if k==-2:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        cache =dict()\n",
    "        def impl(bitmap,total):\n",
    "            key = bitmap << 20 + total\n",
    "            if key in cache:\n",
    "                return cache[key]\n",
    "            i = maxChoosableInteger\n",
    "            # while i:\n",
    "            #     i -= 1\n",
    "            #     if (bitmap & 1 << i):\n",
    "            #         if i + 1 >= total:\n",
    "            #             return True\n",
    "            #         j = maxChoosableInteger\n",
    "            #         while j:\n",
    "            #             j -= 1 \n",
    "            #             if i != j and (bitmap & 1 << j):\n",
    "            #                 if i + 1 + j + 1 < total:\n",
    "            #                     if impl(bitmap ^ (1 << i) ^ (1 << j),total - (i + 1 + j + 1) ):\n",
    "            #                         return True\n",
    "            # return True\n",
    "            while i:\n",
    "                i -= 1\n",
    "                index = 1 << i\n",
    "                if (bitmap & index) > 0:\n",
    "                    if i + 1 >= total or not impl(bitmap ^ index,total - i - 1):\n",
    "                        cache[key] = True\n",
    "                        return True\n",
    "            cache[key] = False\n",
    "            return False\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        init_bitmap = 0\n",
    "        for i in range(maxChoosableInteger):\n",
    "            init_bitmap ^= 1 << i\n",
    "        return impl(init_bitmap,desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        iter_index = list(reversed(range(maxChoosableInteger)))\n",
    "        cache =dict()\n",
    "        def impl(bitmap,total):\n",
    "            if (bitmap,total) in cache:\n",
    "                return cache[(bitmap,total)]\n",
    "            for i in iter_index:\n",
    "                index = 1 << i\n",
    "                if (bitmap & index) > 0:\n",
    "                    if i + 1 >= total:\n",
    "                        return True\n",
    "                    if not impl(bitmap ^ index,total - i - 1):\n",
    "                        cache[(bitmap,total)] = True\n",
    "                        return True\n",
    "            cache[(bitmap,total)] = False\n",
    "            return False\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal:\n",
    "            return False\n",
    "        init_bitmap = 0\n",
    "        for i in range(maxChoosableInteger):\n",
    "            init_bitmap ^= 1 << i\n",
    "        return impl(init_bitmap,desiredTotal)\n",
    "\n",
    "\n",
    "# def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "#         bitmap = 1\n",
    "#         for i in range(maxChoosableInteger-1):\n",
    "#             bitmap = bitmap << 1 + 1\n",
    "#         print(bitmap)\n",
    "#         def impl(choose,total):\n",
    "#             for i in range(len(choose)):\n",
    "#                     next_choose = choose.copy()\n",
    "#                     value = next_choose.pop(i)\n",
    "#                     if value >= total:\n",
    "#                         return True\n",
    "#                     if not impl(next_choose,total - value):\n",
    "#                         return True\n",
    "#             return False\n",
    "#         return impl(list(range(1,maxChoosableInteger+1)),desiredTotal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if maxChoosableInteger >= desiredTotal: return True\n",
    "        if sum(range(maxChoosableInteger+1)) < desiredTotal: return False\n",
    "        @cache\n",
    "        def dfs(mask, s):\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                if mask >> i & 1 == 0:\n",
    "                    if s <= i or not dfs(1 << i | mask, s - i):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(usedNumbers: int, currentTotal: int) -> bool:\n",
    "            for i in range(maxChoosableInteger):\n",
    "                if (usedNumbers >> i) & 1 == 0:\n",
    "                    if currentTotal + i + 1 >= desiredTotal or not dfs(usedNumbers | (1 << i), currentTotal + i + 1):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self,maxChoosableInteger, desiredTotal):\n",
    "        if (1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal: \n",
    "            return False\n",
    "        if maxChoosableInteger >= desiredTotal: \n",
    "            return True\n",
    "\n",
    "        memo = dict()\n",
    "        def win(nums, desiredTotal):\n",
    "            if nums[-1] >= desiredTotal: \n",
    "                return True\n",
    "            hash = str(nums)\n",
    "            if hash in memo: \n",
    "                return memo[hash]\n",
    "            for i in range(len(nums)-1, -1, -1):\n",
    "                next_nums = nums[:i]+nums[i+1:]\n",
    "                if not win(next_nums, desiredTotal - nums[i]):\n",
    "                    memo[hash] = True\n",
    "                    return True\n",
    "            memo[hash] = False\n",
    "            return False\n",
    "\n",
    "        nums = list(range(1, maxChoosableInteger+1))\n",
    "        return win(nums, desiredTotal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "        if desiredTotal > maxChoosableInteger * (maxChoosableInteger + 1) // 2:\n",
    "            return False\n",
    "        @cache\n",
    "        def dp(x, rem):\n",
    "            if rem <= 0:\n",
    "                return False\n",
    "            l = len(bin(x)) - 2\n",
    "            for i in range(l):\n",
    "                if (x >> i) & 1 and not dp(x ^ (1 << i), rem - i - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dp((1 << maxChoosableInteger) - 1, desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        d={}\n",
    "        if (maxChoosableInteger+1)*maxChoosableInteger//2<desiredTotal:\n",
    "            return False\n",
    "        def dfs(used,total):\n",
    "            for i in range(1,maxChoosableInteger+1):\n",
    "                if (1<<i)&used==0:\n",
    "                    if (used|(1<<i),total-i) not in d:\n",
    "                        d[(used|(1<<i),total-i)]=dfs(used|(1<<i),total-i)\n",
    "                    if i>=total or not d[(used|(1<<i),total-i)]:\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0,desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(pre, state):\n",
    "            if pre >= desiredTotal:\n",
    "                return False\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                if not state & (1 << i):\n",
    "                    if not dfs(pre + i, state ^ (1 << i)):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "        if maxChoosableInteger * (maxChoosableInteger + 1) < desiredTotal:\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, mci: int, desiredTotal: int) -> bool:\n",
    "        if (mci+1)*mci >> 1  <= desiredTotal:\n",
    "            return mci&1==1 and (mci+1)*mci >> 1  == desiredTotal\n",
    "        nums=[False]*mci\n",
    "        n = mci\n",
    "        d = {}\n",
    "\n",
    "        def tostr(nums):\n",
    "            return \"\".join([\"1\" if num else \"0\" for num in nums])\n",
    "        def win(total):\n",
    "            if total <=0:\n",
    "                return False\n",
    "            s = tostr(nums)\n",
    "            if s in d:\n",
    "                return d[s]\n",
    "            iswin = False\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if not nums[i]:\n",
    "                    nums[i] = True\n",
    "                    iswin = not win(total-i-1)\n",
    "                    nums[i] = False\n",
    "                    if iswin:\n",
    "                        break\n",
    "            d[s] = iswin\n",
    "            return iswin\n",
    "        return desiredTotal==0 or win(desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal <= maxChoosableInteger:\n",
    "            return True\n",
    "        if sum(range(maxChoosableInteger + 1)) < desiredTotal:\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs( mask, cur_sum, maxChoosableInteger: int, desiredTotal: int):\n",
    "            for i in range(1, maxChoosableInteger + 1):\n",
    "                cur = 1 << i\n",
    "                if cur & mask == 0:\n",
    "                    if cur_sum + i >= desiredTotal or not dfs(cur | mask, cur_sum + i, maxChoosableInteger,\n",
    "                                                                desiredTotal):\n",
    "                        return True\n",
    "            return False\n",
    "        return  dfs(0, 0, maxChoosableInteger, desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal == 0: return True\n",
    "        elif (maxChoosableInteger + 1) * maxChoosableInteger // 2 < desiredTotal: return False\n",
    "        # nums = tuple([n+1 for n in range(maxChoosableInteger)])\n",
    "\n",
    "        @cache\n",
    "        def play(nums, remain, val, target):\n",
    "            if target <= val: return False\n",
    "\n",
    "            for np in range(nums):\n",
    "                if not (1 << np) & remain: continue\n",
    "                tmp = np + val + 1\n",
    "                if tmp >= target: return True\n",
    "                else: \n",
    "                    if not play(nums, remain ^ (1 << (np)), tmp, target):\n",
    "                        return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        return play(maxChoosableInteger, (1 << (maxChoosableInteger)) - 1, 0, desiredTotal)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (1+maxChoosableInteger)*maxChoosableInteger//2 < desiredTotal:\n",
    "            return False\n",
    "        choose = tuple([True for i in range(maxChoosableInteger)])\n",
    "        @cache\n",
    "        def dfs(choose,total):\n",
    "            for i in range(maxChoosableInteger):\n",
    "                if choose[i] == True:\n",
    "                    nx = [choose[j] for j in range(maxChoosableInteger)]\n",
    "                    nx[i] = False\n",
    "                    nx = tuple(nx)\n",
    "                    if total + i + 1 >= desiredTotal or not dfs(nx,total + i + 1):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(choose,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if desiredTotal > (1+maxChoosableInteger) * maxChoosableInteger // 2:\n",
    "            return False\n",
    "        h = [i for i in range(maxChoosableInteger+1)]\n",
    "        q = {}\n",
    "        if desiredTotal == 0:\n",
    "            return True\n",
    "        def dfs(count, s):\n",
    "            if (count, s, tuple(h)) in q:\n",
    "                return q[(count, s, tuple(h))]\n",
    "            if s >= desiredTotal:\n",
    "                if count == 1:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False \n",
    "            if count == 0:\n",
    "                for i in range(1, maxChoosableInteger+1):\n",
    "                    if h[i] == 0:\n",
    "                        continue\n",
    "                    h[i] = 0\n",
    "                    if dfs(1, s+i):\n",
    "                        q[(1, s+i, tuple(h))] = True\n",
    "                        h[i] = i\n",
    "                        q[(0, s, tuple(h))] = True    \n",
    "                        return True \n",
    "                    q[(1, s+i, tuple(h))] = False\n",
    "                    h[i] = i    \n",
    "                q[(0, s, tuple(h))] = False\n",
    "                return False \n",
    "            if count == 1:\n",
    "                for i in range(1, maxChoosableInteger+1):\n",
    "                    if h[i] == 0:\n",
    "                        continue\n",
    "                    h[i] = 0\n",
    "                    if not dfs(0, s+i):\n",
    "                        q[(0, s+i,tuple(h))] = False\n",
    "                        h[i] = i\n",
    "                        q[(1, s,tuple(h))] = False\n",
    "\n",
    "                        return False\n",
    "                    q[(0, s+i,tuple(h))] = True \n",
    "                    h[i] = i\n",
    "                q[(1, s, tuple(h))] = True\n",
    "                return True \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "\n",
    "        dp = {}\n",
    "\n",
    "        if(maxChoosableInteger*(maxChoosableInteger+1)//2 < desiredTotal):\n",
    "            return False\n",
    "\n",
    "        def dfs(turn: int, canChooseInt: List[int], target: int) -> bool:\n",
    "            if(canChooseInt[-1] >= target):\n",
    "                if(turn == 0):\n",
    "                    return True\n",
    "\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if(turn == 0):\n",
    "                    for i in range(len(canChooseInt)):\n",
    "                        t = target-canChooseInt[i]\n",
    "                        cc = canChooseInt[:i]+canChooseInt[i+1:]\n",
    "                        r = False\n",
    "                        if(tuple([1, t]+cc) in dp):\n",
    "                            r = dp[tuple([1, t]+cc)]\n",
    "                        else:\n",
    "                            r = dfs(1, cc, t)\n",
    "                            dp[tuple([1, t]+cc)] = r\n",
    "                        if(r):\n",
    "                            return True\n",
    "                    return False\n",
    "                else:\n",
    "                    for i in range(len(canChooseInt)):\n",
    "                        t = target-canChooseInt[i]\n",
    "                        cc = canChooseInt[:i]+canChooseInt[i+1:]\n",
    "                        r = True\n",
    "                        if(tuple([0, t]+cc) in dp):\n",
    "                            r = dp[tuple([0, t]+cc)]\n",
    "                        else:\n",
    "                            r = dfs(0, cc, t)\n",
    "                            dp[tuple([0, t]+cc)] = r\n",
    "                        if(not r):\n",
    "                            return False\n",
    "                    return True\n",
    "        return dfs(0, [i for i in range(1, maxChoosableInteger+1)], desiredTotal)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:\n",
    "        if (maxChoosableInteger + 1) * maxChoosableInteger < 2 * desiredTotal:\n",
    "            return False\n",
    "\n",
    "        nums = list(range(1, maxChoosableInteger+1))\n",
    "        @lru_cache(None)\n",
    "        def check(flag, target):\n",
    "            right = maxChoosableInteger-1\n",
    "            while flag[right] == \"0\":\n",
    "                right -= 1\n",
    "            \n",
    "            left = 0\n",
    "            while flag[left] == \"0\":\n",
    "                left += 1\n",
    "    \n",
    "            if target <= nums[right]:\n",
    "                return True\n",
    "\n",
    "            if target <= nums[right] + nums[left]:\n",
    "                return False\n",
    "\n",
    "            ans = False\n",
    "            for i in range(right+1):\n",
    "                if flag[i] == \"1\":\n",
    "                    ans |= not check(flag[:i] + \"0\" + flag[i+1:], target-nums[i])\n",
    "                if ans: return True\n",
    "            return False\n",
    "            \n",
    "        return check(\"1\"*maxChoosableInteger, desiredTotal)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
